// https://leetcode.cn/problems/merge-sorted-array/

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> res(m + n);
        int p1 = 0;
        int p2 = 0;
        while (p1 < m && p2 < n) {
            if (nums1[p1] < nums2[p2]) {
                res[p1 + p2] = nums1[p1];
                ++p1;
            } else {
                res[p1 + p2] = nums2[p2];
                ++p2;
            }
        }
        while (p1 < m) {
            res[p1 + p2] = nums1[p1];
            ++p1;
        }
        while (p2 < n) {
            res[p1 + p2] = nums2[p2];
            ++p2;
        }
        nums1.assign(res.begin(), res.end());
    }
};

// 法二：逆向双指针
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p1 + p2 + 1] = nums1[p1];
                --p1;
            } else {
                nums1[p1 + p2 + 1] = nums2[p2];
                --p2;
            }
        }
        while (p1 >= 0) {
            nums1[p1 + p2 + 1] = nums1[p1];
            --p1;
        }
        while (p2 >= 0) {
            nums1[p1 + p2 + 1] = nums2[p2];
            --p2;
        }
    }
};